package th.retrofit.lib;

import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

public class Solution939 {

    public int minAreaRect(int[][] points) {
        Map<Integer, List<Integer>> xMap = new TreeMap<>();
        for (int[] point : points) {
            xMap.putIfAbsent(point[0], new LinkedList<>());
            xMap.get(point[0]).add(point[1]);
        }
        int minArea = Integer.MAX_VALUE;
        Map<Integer, Integer> lastX = new HashMap<>();
        Set<Integer> set = xMap.keySet();
        for (Integer x : set) {
            List<Integer> list = xMap.get(x);
            Collections.sort(list);
            for (int i = 0; i < list.size() - 1; i++) {
                for (int j = i + 1; j < list.size(); j++) {
                    int key = 40001 * list.get(i) + list.get(j);
                    if (lastX.containsKey(key)) {
                        int area = (x - lastX.get(key)) * (list.get(j) - list.get(i));
                        minArea = Math.min(minArea, area);
                    }
                    lastX.put(key, x);
                }
            }
        }
        return minArea == Integer.MAX_VALUE ? 0 : minArea;
    }


    public static void main(String[] args) {
        int[][] points = new int[][]{{36219,4673},{26311,36047},{26311,4673},{36219,16024},{17010,16024},{26311,6287},{22367,6287},{17010,36047},{17010,6287},{22367,16024},{36219,6287},{22367,4673},{17010,4673},{36219,36047}};
        System.out.println(new Solution939().minAreaRect(points));
    }

}
